package com.nine.algorithm.leetcode.list;

/**
 * @author nine
 * @version 1.0
 * @description 环形链表，检测环的入口
 * @date 24/5/7 23:13
 */
public class Leetcode142 {

	public static void main(String[] args) {
		// 构造带环链表
		ListNode n12 = new ListNode(12, null);
		ListNode n11 = new ListNode(11, n12);
		ListNode n10 = new ListNode(10, n11);
		ListNode n9 = new ListNode(9, n10);
		ListNode n8 = new ListNode(8, n9);
		ListNode n7 = new ListNode(7, n8);
		ListNode n6 = new ListNode(6, n7);
		ListNode n5 = new ListNode(5, n6);
		ListNode n4 = new ListNode(4, n5);
		ListNode n3 = new ListNode(3, n4);
		ListNode n2 = new ListNode(2, n3);
		ListNode n1 = new ListNode(1, n2);
		n12.next = n8;

		System.out.println(detectCycle(n1));
	}

	private static ListNode detectCycle(ListNode head) {
		ListNode h = head;  // 兔子
		ListNode t = head;  // 乌龟
		while (h != null && h.next != null) {
			t = t.next;
			// 一次跑两个，需要在循环时加上 h.next != null
			h = h.next.next;
			if (h == t) {
				// 进入第二阶段
				t = head;
				while (true) {
					// 第二次相遇，这个点就是环的入口
					if (t == h) {
						return t;
					}
					// 为了防止是圆环的情况，这个移动指针需要放在判断之后
					t = t.next;
					h = h.next;
				}
			}
		}
		return null;
	}

}
